package btree;

import btree.base.TreeNode;

public class Solution_543 {

    int ans;

    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return ans;
    }

    private int dfs(TreeNode root) {
        if (root == null) return -1;
        int leftDepth = dfs(root.left) + 1;
        int rightDepth = dfs(root.right) + 1;
        ans = Math.max(ans, leftDepth + rightDepth);
        return Math.max(leftDepth, rightDepth);
    }
}
